class ZHeap:
    def __init__(self, items=None, weight_key=None):
        self.items = items
        self.heapsize = len(self.items)
        self.weight_key = weight_key
        self.build_min_heap()

    def val(self, item):
        if self.weight_key is None:
            return item
        else:
            return item[self.weight_key]


    def left(self, i):
        return 2 * i + 1

    def right(self, i):
        return 2 * i + 2

    def parent(self, i):
        return (i - 1) // 2

    def MIN_HEAPIFY(self, i):
        # O(log(n))
        l = self.left(i)
        r = self.right(i)

        if l < self.heapsize and self.val(self.items[l]) < self.val(self.items[i]):
            smallest = l
        else:
            smallest = i

        if r < self.heapsize and self.val(self.items[r]) < self.val(self.items[smallest]):
            smallest = r

        if smallest != i:
            self.items[i], self.items[smallest] = self.items[smallest], self.items[i]
            self.MIN_HEAPIFY(smallest)


    def insert(self, item):
        # O(log(n))
        self.items.append(item)
        leaf = len(self.items) - 1
        node = self.parent(leaf)
        while node >= 0:
            if self.val(self.items[node]) > self.val(self.items[leaf]):
                self.items[node], self.items[leaf] = self.items[leaf], self.items[node]
                leaf = node
                node = self.parent(node)
            else:
                break
        self.heapsize += 1


    def pop(self):
        # O(log(n))
        last = len(self.items) - 1
        if last < 0:
            return None
        self.items[0], self.items[last] = self.items[last], self.items[0]
        val = self.items.pop()
        self.heapsize -= 1
        self.MIN_HEAPIFY(0)
        return val


    def build_min_heap(self):
        # 建立最小堆, O(nlog(n))
        i = self.parent(len(self.items) - 1)
        while i >= 0:
            self.MIN_HEAPIFY(i)
            i -= 1


    def size(self):
        return len(self.items)

    def __str__(self):
        return self.items.__str__()
